#ifndef XX_COMMON_LISTANDQUEUE_HH
#define XX_COMMON_LISTANDQUEUE_HH
#include "internal.h"

template<typename T>
struct x_item {
	T*		data;
	x_item*	next;
};

#define REMOVE_FREE(T,Q)			\
	do{								\
		T* Obj = Q.RemoveHead();	\
		if (0 == Obj) {				\
			break;					\
		}							\
		free(Obj);					\
	} while (true);

#define REMOVE_DELETE(T,Q)			\
	do{								\
		T* Obj = Q.RemoveHead();	\
		if (0 == Obj) {				\
			break;					\
		}							\
		delete Obj;					\
	} while (true);


template<typename T>
class xQueue
{
public:
	xQueue();

	virtual ~xQueue();

	virtual T* RemoveHead();

	virtual int QuePush(T* data);

protected:
	int			   mSize;
	x_item<T>*	   mLast;
	x_item<T>*	   mFirst;
#ifndef WIN32
	pthread_mutex_t  mMutex;
#else
	CRITICAL_SECTION mMutex;
#endif
};

template<typename T>
xQueue<T>::xQueue()
{
	mSize = 0;
	mLast = NULL;
	mFirst = NULL;
#ifndef WIN32
	pthread_mutex_init(&mMutex, NULL);
#else
	InitializeCriticalSection(&mMutex);
#endif
}

template<typename T>
xQueue<T>::~xQueue()
{
#ifdef WIN32
	DeleteCriticalSection(&mMutex);
#else
	pthread_mutex_destroy(&mMutex);
#endif
}

template<typename T>
int xQueue<T>::QuePush(T* data)
{
	x_item<T>* newItem = (x_item<T>*)malloc(sizeof(x_item<T>));

	newItem->data = data;
	newItem->next = 0;

#ifndef WIN32
	pthread_mutex_lock(&mMutex);
#else
	EnterCriticalSection(&mMutex);
#endif
	if (NULL != mLast) {
		mLast->next = newItem;
	}
	else {
		mFirst = newItem;
	}
	mLast = newItem;
	++mSize;
#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
#else
	LeaveCriticalSection(&mMutex);
#endif
	return 0;
}

template<typename T>
T* xQueue<T>::RemoveHead()
{
	T* ItemData = NULL;
	x_item<T>* freeItem = NULL;

#ifndef WIN32
	pthread_mutex_lock(&mMutex);
#else
	EnterCriticalSection(&mMutex);
#endif
	if (NULL != mFirst) {
		freeItem = mFirst;
		mFirst = mFirst->next;
		if (mFirst == NULL) {
			mLast = NULL;
		}
		--mSize;
	}
#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
#else
	LeaveCriticalSection(&mMutex);
#endif

	if (NULL != freeItem) {
		ItemData = freeItem->data;
		free(freeItem);
	}
	return ItemData;
}

template<typename Ty>
struct QueueItem {
	Ty* data;
	QueueItem* next;
};

template<typename Ty>
class xQueueEx
{
public:
	xQueueEx();

	virtual ~xQueueEx();

	virtual void QueQuit();

	virtual Ty* RemoveHead();

	virtual int  QuePush(Ty* data);

	virtual Ty* RemoveHead(int* plen);

protected:
	int				 mSize;
	bool			 mEnd;
	QueueItem<Ty>*   mLast;
	QueueItem<Ty>*   mFirst;
#ifdef WIN32
	HANDLE			 mCondition;
	CRITICAL_SECTION m_csSection;
#else
	pthread_mutex_t  mMutex;
	pthread_cond_t	 mCondition;
#endif
};

template<typename Ty>
xQueueEx<Ty>::xQueueEx()
{
	mSize = 0;
	mEnd = false;
	mFirst = mLast = 0;
#ifndef WIN32
	pthread_mutex_init(&mMutex, NULL);
	pthread_cond_init(&mCondition, NULL);
#else
	InitializeCriticalSection(&m_csSection);
	mCondition = CreateEvent(NULL, FALSE, FALSE, NULL);
#endif
}

template<typename Ty>
xQueueEx<Ty>::~xQueueEx()
{
#ifdef WIN32
	CloseHandle(mCondition);
	DeleteCriticalSection(&m_csSection);
#else
	pthread_mutex_destroy(&mMutex);
	pthread_cond_destroy(&mCondition);
#endif
}

template<typename Ty>
Ty* xQueueEx<Ty>::RemoveHead()
{
	Ty* ItemData = 0;
	QueueItem<Ty>* freeItem = 0;
#ifndef WIN32
	pthread_mutex_lock(&mMutex);
#else
	EnterCriticalSection(&m_csSection);
#endif

	if (NULL != mFirst) {
		freeItem = mFirst;
		mFirst = mFirst->next;
		if (mFirst == 0) {
			mLast = 0;
		}
	}

#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
#else
	LeaveCriticalSection(&m_csSection);
#endif
	if (NULL != freeItem) {
		ItemData = freeItem->data;
		free(freeItem);
	}
	return ItemData;
}

template<typename Ty>
int xQueueEx<Ty>::QuePush(Ty* data)
{
	QueueItem<Ty>* newItem = (QueueItem<Ty>*)malloc(sizeof(QueueItem<Ty>));
	newItem->data = data;
	newItem->next = 0;

#ifndef WIN32
	pthread_mutex_lock(&mMutex);
#else
	EnterCriticalSection(&m_csSection);
#endif
	if (NULL != mLast) {
		mLast->next = newItem;
	}
	else {
		mFirst = newItem;
	}
	mLast = newItem;

	++mSize;

#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
	pthread_cond_signal(&mCondition);
#else
	LeaveCriticalSection(&m_csSection);
	SetEvent(mCondition);
#endif
	return XX_ERR_NONE;
}

template<typename Ty>
Ty* xQueueEx<Ty>::RemoveHead(int* plen)
{
	Ty* ItemData = 0;
	QueueItem<Ty>* freeItem = 0;
#ifndef WIN32
	pthread_mutex_lock(&mMutex);

	while (!mEnd && (0 == mSize)) {
		pthread_cond_wait(&mCondition, &mMutex);
	}
#else

	EnterCriticalSection(&m_csSection);

	while (!mEnd && (0 == mSize)) {
		LeaveCriticalSection(&m_csSection);
		WaitForSingleObject(mCondition, INFINITE);
		EnterCriticalSection(&m_csSection);
	}
#endif

	if (NULL != mFirst) {
		freeItem = mFirst;
		mFirst = mFirst->next;
		if (mFirst == 0) {
			mLast = 0;
		}
		--mSize;
	}

	*plen = mSize;

#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
#else
	LeaveCriticalSection(&m_csSection);
#endif

	if (NULL != freeItem) {
		ItemData = freeItem->data;
		free(freeItem);
	}

	return ItemData;
}

template<typename Ty>
void xQueueEx<Ty>::QueQuit()
{
#ifndef WIN32
	pthread_mutex_lock(&mMutex);
#else
	EnterCriticalSection(&m_csSection);
#endif
	mEnd = true;
#ifndef WIN32
	pthread_mutex_unlock(&mMutex);
	pthread_cond_signal(&mCondition);
#else
	LeaveCriticalSection(&m_csSection);
	SetEvent(mCondition);
#endif
}

struct __POSITION { };
typedef __POSITION* POSITION;

template<typename T>
struct CNode {
	uint64 uKey;
	char*  sKey;
	T*	   data;
	CNode* pNext;
	CNode* pPrev;
};

template<typename T>
class xlist
{
public:
	xlist();
	virtual ~xlist();

	int			GetCount() const;
	bool		IsEmpty() const;

	T*			RemoveHead();
	T*			RemoveTail();
	void		RemoveAt(T* item);
	void		RemoveAt(POSITION position);

	void		AddTail(T* item);
	void		AddTail(char* Key,T* item);
	void		AddTail(uint64 Key,T* item);

	POSITION	GetHead() const;
	T*			GetNext(POSITION& rPosition);
	T*			GetPrev(POSITION& rPosition);
	T*			GetTail();

	T*			find(T* item);
	T*			find(uint64 key);
	T*			find(const char* key);

private:
	int 		m_nCount;
	CNode<T>*	m_pNodeHead;
	CNode<T>*	m_pNodeTail;

	void    	FreeNode(CNode<T>*);
	CNode<T>*	AllocNode(CNode<T>*, CNode<T>*);
};

template<typename T>
xlist<T>::xlist()
{
	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = 0;
}

template<typename T>
xlist<T>::~xlist()
{

}

template<typename T>
CNode<T>* xlist<T>::AllocNode(CNode<T>* pPrev, CNode<T>* pNext)
{
	CNode<T>* pNodeFree = (CNode<T>*)malloc(sizeof(CNode<T>));
	if (0 == pNodeFree)
		return 0;
	pNodeFree->pPrev = pPrev;
	pNodeFree->pNext = pNext;
	pNodeFree->uKey = 0;
	pNodeFree->sKey = 0;
	pNodeFree->data = 0;
	m_nCount++;
	return pNodeFree;
}

template<typename T>
void xlist<T>::FreeNode(CNode<T>* pNode)
{
	if (pNode == 0) {
		return;
	}
	free(pNode);
	pNode = NULL;//
	m_nCount--;
}

template<typename T>
void xlist<T>::AddTail(T* item)
{
	CNode<T>* pNewNode = AllocNode(m_pNodeTail, NULL);
	if (NULL == pNewNode)
		return;
	pNewNode->data = item;
	if (m_pNodeTail != NULL) {
		m_pNodeTail->pNext = pNewNode;
	}
	else {
		m_pNodeHead = pNewNode;
	}
	m_pNodeTail = pNewNode;
}

template<typename T>
void xlist<T>::AddTail(char* Key,T* item)
{
	CNode<T>* pNewNode = AllocNode(m_pNodeTail, NULL);
	if (NULL == pNewNode)
		return;
	pNewNode->sKey = Key;
	pNewNode->data = item;
	if (m_pNodeTail != NULL) {
		m_pNodeTail->pNext = pNewNode;
	}
	else {
		m_pNodeHead = pNewNode;
	}
	m_pNodeTail = pNewNode;
}

template<typename T>
void xlist<T>::AddTail(uint64 Key,T* item)
{
	CNode<T>* pNewNode = AllocNode(m_pNodeTail, NULL);
	if (NULL == pNewNode)
		return;

	pNewNode->uKey = Key;
	pNewNode->data = item;
	if (m_pNodeTail != NULL) {
		m_pNodeTail->pNext = pNewNode;
	}
	else {
		m_pNodeHead = pNewNode;
	}
	m_pNodeTail = pNewNode;
}

template<typename T>
T* xlist<T>::RemoveHead()
{
	if (0 == m_pNodeHead)
		return 0;
	CNode<T>* pOldNode = m_pNodeHead;
	void* returnValue = pOldNode->data;

	m_pNodeHead = pOldNode->pNext;

	if (m_pNodeHead != 0)
		m_pNodeHead->pPrev = 0;
	else
		m_pNodeTail = 0;
	FreeNode(pOldNode);
	return (T*)returnValue;
}

template<typename T>
T* xlist<T>::RemoveTail()
{
	CNode<T>* pOldNode = m_pNodeTail;
	void* returnValue = pOldNode->data;

	m_pNodeTail = pOldNode->pPrev;
	if (m_pNodeTail != 0)
		m_pNodeTail->pNext = 0;
	else
		m_pNodeHead = 0;
	FreeNode(pOldNode);
	return (T*)returnValue;
}

template<typename T>
void xlist<T>::RemoveAt(T* item)
{
	for (CNode<T>* pOldNode = m_pNodeHead; pOldNode != NULL;) {
		if (pOldNode->data == item) {
			if (pOldNode == m_pNodeHead) {
				m_pNodeHead = pOldNode->pNext;
			}
			else {
				pOldNode->pPrev->pNext = pOldNode->pNext;
			}
			if (pOldNode == m_pNodeTail) {
				m_pNodeTail = pOldNode->pPrev;
			}
			else {
				pOldNode->pNext->pPrev = pOldNode->pPrev;
			}
			FreeNode(pOldNode);
			break;
		}
		pOldNode = pOldNode->pNext;
	}
}

template<typename T>
void xlist<T>::RemoveAt(POSITION position)
{
	CNode<T>* pOldNode = (CNode<T>*)position;
	if (pOldNode == m_pNodeHead) {
		m_pNodeHead = pOldNode->pNext;
	}
	else {
		pOldNode->pPrev->pNext = pOldNode->pNext;
	}
	if (pOldNode == m_pNodeTail) {
		m_pNodeTail = pOldNode->pPrev;
	}
	else {
		pOldNode->pNext->pPrev = pOldNode->pPrev;
	}
	FreeNode(pOldNode);
}

template<typename T>
int xlist<T>::GetCount() const
{
	return m_nCount;
}

template<typename T>
bool xlist<T>::IsEmpty() const
{
	return m_nCount == 0;
}

template<typename T>
POSITION xlist<T>::GetHead() const
{
	return (POSITION)m_pNodeHead;
}

template<typename T>
T* xlist<T>::GetNext(POSITION& rPosition)
{
	CNode<T>* pNode = (CNode<T>*)rPosition;
	rPosition = (POSITION)pNode->pNext;
	return (T*)pNode->data;
}

template<typename T>
T* xlist<T>::GetTail() {
	CNode<T>* pNode = m_pNodeTail;
	if (m_pNodeTail != 0)
		return m_pNodeTail->data;
	else
		return NULL;
}

template<typename T>
T* xlist<T>::GetPrev(POSITION& rPosition)
{
	CNode<T>* pNode = (CNode<T>*)rPosition;
	rPosition = (POSITION)pNode->pPrev;
	return pNode->data;
}

template<typename T>
T* xlist<T>::find(T* item)
{
	for (CNode<T>* pNode = m_pNodeHead; pNode != 0;) {
		if (pNode->data == item) {
			return pNode->data;
		}
		pNode = pNode->pNext;
	}
	return NULL;
}

template<typename T>
T* xlist<T>::find(const char* key)
{
	for (CNode<T>* pNode = m_pNodeHead; pNode != 0;) {
		if(0 == strcmp(pNode->sKey,key)){
			return pNode->data;
		}
		pNode = pNode->pNext;
	}
	return NULL;
}

template<typename T>
T* xlist<T>::find(uint64 key)
{
	for (CNode<T>* pNode = m_pNodeHead;pNode != 0;) {
		if (pNode->uKey == key) {
			return pNode->data;
		}
		pNode = pNode->pNext;
	}
	return NULL;
}

#endif
